package DynamicProgramming;//给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
//
// 在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单
//元格中所有整数的乘积。 
//
// 返回 最大非负积 对 10⁹ + 7 取余 的结果。如果最大积为负数，则返回 -1 。 
//
// 注意，取余是在得到最大积之后执行的。 
//
// 
//
// 示例 1： 
//
// 输入：grid = [[-1,-2,-3],
//             [-2,-3,-3],
//             [-3,-3,-2]]
//输出：-1
//解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1
// 
//
// 示例 2： 
//
// 输入：grid = [[1,-2,1],
//             [1,-2,1],
//             [3,-4,1]]
//输出：8
//解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)
// 
//
// 示例 3： 
//
// 输入：grid = [[1, 3],
//             [0,-4]]
//输出：0
//解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)
// 
//
// 示例 4： 
//
// 输入：grid = [[ 1, 4,4,0],
//             [-2, 0,0,1],
//             [ 1,-1,1,1]]
//输出：2
//解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)
// 
//
// 
//
// 提示： 
//
// 
// 1 <= rows, cols <= 15 
// -4 <= grid[i][j] <= 4 
// 
// Related Topics 数组 动态规划 矩阵 👍 36 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class maxProductPath {
    public  static int maxProductPath(int[][] grid) {
        int DIVIDE = 1_000_000_000 + 7;
        int rows = grid.length;
        int cols = grid[0].length;
        //由题意得，只能向右和下移动，因此当前位置只能从左方和下方过来.
        int[][] dp = new int[rows][cols];
        //dp[i][j]表示 i,j这个位置上得最大积，取决于dp[i][j-1] * grid[i][j] 和 dp[i-1][j]* grid[i][j]
        int rown = grid[0][0];
        int coln = grid[0][0];
        dp[0][0] = grid[0][0];
        //初始化,第一行和第一列
        for(int i=1;i<cols;i++) {
            rown *= grid[0][i];
            dp[0][i] = rown;
        }
        for (int i = 1; i < rows; i++) {
            coln *= grid[i][0];
            dp[i][0] = coln;
        }


        //动态规划
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                dp[i][j] = Math.max(dp[i][j-1] * grid[i][j] % DIVIDE, dp[i-1][j] * grid[i][j] % DIVIDE);
            }
        }

        //如果最终是负数 返回 -1
        return dp[rows-1][cols-1] < 0 ? -1 : dp[rows-1][cols-1];
    }

    public static void main(String[] args) {
        int[][] ints = new int[3][4];
        ints[0] = new int[]{1, 4, 4, 0};
        ints[1] = new int[]{-2, 0, 0, 1};
        ints[2] = new int[]{1, -1, 1, 1};
        System.out.println(maxProductPath(ints));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
